CSE 311: Section 6

Task 1 – RegEx to NFA

1. Convert the regular expression “$(11 \cup (01)^*) 00$” to an NFA using the algorithm from lecture. You may skip adding $\varepsilon$-transitions for concatenation if they are obviously unnecessary, but otherwise, you should precisely follow the construction from lecture.

2. Convert the regular expression “$((0 \cup 1) (01)^*)^*$” to an NFA using the algorithm from lecture.

Task 2 – Irregularity

1. Let $\Sigma = \{0, 1\}$. Prove that $\{0^n1^n0^n\;:\; n \geq 0\}$ is not regular.

2. Let $\Sigma = \{0, 1, 2\}$. Prove that $\{0^n(12)^m\;:\; n \geq m \geq 0\}$ is not regular.

Task 3 – Countability

For proving countability, you must use one of the following strategies:

• Enumeration

• Dovetailing

• Subset of a countable set

• Using a surjection (onto function) $f:\mathbb{N} \to S$

• Using an injection (one-to-one function) $f:S \to \mathbb{N}$
  

For proving uncountability, you must show there exists no enumeration of the elements of $S$ (there exists no surjection $f:\mathbb{N} \to S$). This can be done using diagonalization.

1. Prove that $\{3x\;:\;x \in \mathbb{N}\}$ is countable.

2. Prove that $\mathcal{P}(\mathbb{N})$ is uncountable.

3. Show that $\mathbb{N} \times \mathbb{N}$ is countable.

    Hint: How did we show that the rationals were countable?

4. Show that the countable union of countable sets is countable. That is, given a collection of sets $S_1, S_2, S_2, \ldots$ such that $S_i$ is countable for all $i \in \mathbb{N}$, show that the following is countable:

   $$S = S_1 \cup S_2 \cup \cdots = \{ x : \text{$x \in S_i$ for some $i$} \}$$

    Hint: Find a way of labeling the elements and see if you can apply the previous part to construct an onto function from $\mathbb{N}$ to $S$.

Task 4 – NFAs to DFAs

1. Convert the following NFA to a DFA for the same language:

   

2. Convert the following NFA to a DFA for the same language: